//一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [4,1,4,6]
//输出：[1,6] 或 [6,1]
// 
//
// 示例 2： 
//
// 输入：nums = [1,2,10,4,1,4,3,3]
//输出：[2,10] 或 [10,2] 
//
// 
//
// 限制： 
//
// 
// 2 <= nums.length <= 10000 
// 
//
// 
// 👍 201 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：数组中数字出现的次数
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P剑指_offer_56_i_ShuZuZhongShuZiChuXianDeCiShuLcof {
    public static void main(String[] args) {
        Solution solution = new P剑指_offer_56_i_ShuZuZhongShuZiChuXianDeCiShuLcof().new Solution();
        int[] nums = solution.singleNumbers(MyUtil.createArray(1, 2, 10, 4, 1, 4, 3, 3));
        MyUtil.printInt(nums);
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 核心思想，按最低位为1分成两个组
     */
    class Solution {
        public int[] singleNumbers(int[] nums) {
            int m = 0, a = 0, b = 0;
            for (int i : nums) {
                m ^= i;
            }
            m = m & (-m);
            for (int i : nums) {
                if ((i & m) == 0) {
                    a ^= i;
                } else {
                    b ^= i;
                }
            }
            return new int[]{a, b};
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}